package demo;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-06-22
 * Time: 10:35
 */
public class BinaryTree {
    //穷举创建二叉树
    //前中后序遍历
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val =val;
        }
    }

    public TreeNode root;//根节点

    //创造一颗二叉树
    public TreeNode createTree(){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node8 = new TreeNode(8);

        node1.left = node2;
        node1.right = node4;
        node2.left = node3;
        node2.right = node8;
        node4.left = node5;
        node4.right = node6;
        return node1;
    }


    // 前序遍历-->根  左  右
    void preOrder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历  左根右
    void inOrder(TreeNode root){
        if(root==null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    // 后序遍历  左右根
    void postOrder(TreeNode root){
        if(root==null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    // 获取树中节点的个数--->遍历思路
    public static int cnt =0;
    void size1(TreeNode root){
        if(root==null) return ;
        cnt++;
        size1(root.left);
        size1(root.right);
    }

    // 获取树中节点的个数-->子问题思路
    int size2(TreeNode root){
        if(root==null) return 0;
        int leftTree = size2(root.left);
        int rightTree = size2(root.right);
        return leftTree+rightTree+1;
    }

    //获取叶子节点的个数-->遍历思路
    public static int leafSize =0;
    void getLeafNodeCount1(TreeNode root){
        if(root==null){
            return ;
        }
        if(root.left==null&&root.right==null){
            leafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    // 子问题思路-求叶子结点个数
    int getLeafNodeCount2(TreeNode root){
        //左子树叶子结点的个数+右子树叶子结点的个数
        if(root==null) return 0;
        if(root.left==null&&root.right==null) return 1;
        int leftTree = getLeafNodeCount2(root.left);
        int rightTree = getLeafNodeCount2(root.right);
        return leftTree+rightTree;
    }

    //获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root,int k){
        //当k==1时不要递归了
        //root==null
        if(root==null) return 0;
        if(k==1) return 1;
        int leftTree = getKLevelNodeCount(root.left,k-1);
        int rightTree = getKLevelNodeCount(root.right,k-1);

        return leftTree+rightTree;

    }
    // 获取二叉树的高度-->二叉树的最大深度
    int getHeight(TreeNode root){
        if(root==null) return 0;
        int leftTree = getHeight(root.left);
        int rightTree = getHeight(root.right);
        return leftTree>rightTree?leftTree+1:rightTree+1;
    }
    //检测值为value的元素是否存在
    TreeNode find(TreeNode root, int val){
        if(root==null) return null;
        if(root.val==val){
            return root;
        }
        TreeNode leftTree =find(root.left,val);
        if(leftTree!=null){
            return leftTree;
        }
        TreeNode rightTree = find(root.right,val);
        if(rightTree!=null){
            return rightTree;
        }
        return null;
    }
    //层序遍历
    void levelOrder2(TreeNode root){
         //利用队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
    }

    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int sz = queue.size();
            List<Integer> list = new ArrayList<>();
            while(sz>0){
                TreeNode cur = queue.poll();
                list.add(cur.val);
                sz--;
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            ret.add(list);
        }
        return ret;
    }
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root){
        if(root==null){
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        //遍历这个队列
        while(!queue.isEmpty()){
            if(queue.peek()!=null){
                return false;
            }
            queue.poll();
        }
        return true;
    }


}
